1. Field of the Invention
The present invention generally relates to random number generation. More specifically, a fairness checker and correction logic module provides a provably fair random number generator.
2. Description of the Related Art
Random numbers are commonly used in areas such as communication, cryptography, and even games, where the property of interest is the generation of hard to guess numbers. Random number generators are also used in arbitration logic, wherein the property of interest is to avoid fixed or rotating priority.
For example, arbiters are used for restricting access requests to shared resources, as when there are more number of requests than the maximum number requests that can be satisfied concurrently, in such applications as access to cache directory, shared bus, etc. Arbiters are commonly based on one of several priority functions, including:                fixed (certain requests always have higher priority than others);        round-robin (strict rotation of priority assignment); and        random (any request can have the highest priority, at random).        
In random priority arbitration, any request can become the highest priority request at random. For example, as demonstrated by the arbitration scheme 100 in FIG. 1, request i gets its turn at time t when the value of random number r(t)=ƒ(i), where ƒ(i) is a function of i. The goal of this arbitration 100 is to provide unbiased service to all requests.
Thus, pseudo random number generators such as LFSR (linear feedback shift register) have many uses in electronic systems such as microprocessors and peripheral chips. For example, LFSR-based arbitration logic is used in several places in a processor such as in the logic used for restricting multiple concurrent accesses to cache directories and shared buses. An LFSR is used in such arbiters to assign random priority to the input requests.
It is often necessary to have the sequence of random numbers generated by a random number generator adhere to certain desired fairness properties. For example, in order to provide fairness to the input requests, a random priority based arbitration logic must be starvation free (i.e., it does not starve any requests indefinitely or beyond a certain number of cycles). LFSR-based random priority arbiters are commonly used for granting a subset of several concurrent read and write requests to access the cache directory in every cycle. In such random priority-based arbiters, one of the pending requests is granted access to the cache directory based on the random number generated by the LFSR logic in the current cycle. A request will be starved if the specific random number corresponding to the request is not generated by the LFSR for a long time.
Clearly, delaying a directory access request beyond a certain number of cycles can have serious performance impact. Therefore, in real applications, it is not sufficient to prove that the random number generator produces a random number sequence because it only proves that any given random number will be generated eventually (i.e., any given request will be granted eventually). We must also be able to guarantee that any unique random number will be generated within an acceptable finite time interval in order to meet the expected fairness properties of the arbiter.
Main properties of random numbers include predictability and distribution. The property of predictability means that it is highly unpredictable to be random, with no repeating sequences. The property of distribution requires a uniform frequency distribution, meaning that each random number must have the same frequency in an infinitely long sequence.
True random numbers are hard to generate, leading to the many pseudo-random number generators commonly implemented. There are literally hundreds of patents and patent applications related to random number generation, all of which seem to focus on the properties mentioned above, and LFSR (Linear Feedback Shift Register) is perhaps the most popular one currently used.
For example, US Patent Application Publication No. US 20020159590 to Ikeda, entitled “Random number generator which can generate a random number based on an uniform distribution”, describes a technique for generating random numbers that is guaranteed to have a uniform distribution. Their technique cannot generate random numbers that has bounded fairness, the problem solved by the present invention.
A technical paper by Dershowitz et al., entitled “Bounded Fairness”, discusses the concept bounded fairness in more detail.
As a second example, US Patent Application Publication No. US 20050193045 to Yamamoto et al., entitled “Random number generator and probability generator”, describes a technique for generating 1-bit and multi-bit random numbers that has a specific probability distribution. The goal of their technique is to realize a high speed and high performance probability generator without regularity, correlativity and periodicity. This scheme also cannot generate random numbers with guaranteed bounded fairness properties, as can the present invention.
US Patent Application Publication No. US 20030065691 to Schmidt, entitled “Method and apparatus for generating random numbers with improved statistical properties”, describes a technique for combining a plurality of random number generators into a combined random number generator such that the combined random number generator produces random number sequences that has the least amount of repeated patterns. The technique is based on using the inter-arrival time of individual random number generators to generate a combined random number sequence that has uniformly distributed random numbers. This scheme does not address the problem solved by present invention of generating random numbers with guaranteed bounded fairness properties.
In U.S. Pat. No. 6,408,317, issued Jun. 18, 2002, to Djakovic, entitled “Random number conditioner”, is described a technique aimed at generating sequence of random numbers that can not be easily predicted. It uses a random number generator “conditioner” that uses an XOR function to combine the input bit stream with a checksum of it and new LFSR generated random number sequence. This scheme cannot generate random numbers with guaranteed bounded fairness properties.
Thus, a need continues to exist to provide a method and structure for a provably fair random number generator.